package huaweiod.first;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 华为OD机试真题 Java 实现【最大报酬】【2022.11 Q4 新题】
 * 40 3
 * 20 10
 * 20 20
 * 20 5
 */
public class A_2023_57_MaxReturn {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int N = in.nextInt();
        List<Integer[]> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int t = in.nextInt();
            int w = in.nextInt();
            // 第i个，时长，报酬
            list.add(new Integer[]{i, t, w});
        }
        // 动态规范
        int[][] dp = new int[N + 1][T + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= T; j++) {
                Integer[] job = list.get(i - 1);
                int t = job[1];
                int w = job[2];
                if (j >= t) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - t] + w);
                }
            }
        }
        System.out.println(dp[N][T]);
    }
}
